package com.leetcode.p300;

import java.util.HashMap;

public class Test343 {

    private HashMap<Integer, Integer> hashMap = new HashMap<>();

    private int max3(int a1, int a2, int a3) {
        return Math.max(Math.max(a1, a2), a3);
    }

    public int integerBreak(int n) {
        if (n <= 2) {
            return 1;
        }

        if (hashMap.containsKey(n)) {
            return hashMap.get(n);
        }

        int currentMax = 0;
        for (int i = 1; i <= n - 1; i++) {
            currentMax = max3(currentMax, i * integerBreak(n - i), i * (n - i));
        }
        hashMap.put(n, currentMax);
        return currentMax;
    }

    public static void main(String[] args) {
        Test343 test = new Test343();

//        63 = 9*7 或 3*3*7
//        891= 9*9*9
//        System.out.println(test.integerBreak(63));
        System.out.println(test.integerBreak(10));
    }
}
